package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/11/6
 * @description: 129. 求根到叶子节点数字之和
 * 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
 *
 * 例如，从根到叶子节点路径 1->2->3 代表数字 123。
 * 计算从根到叶子节点生成的所有数字之和。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SumRoottoLeafNumbers129B {

	public int sumNumbers(TreeNode root) {
		if (root==null){
			return 0;
		}

		List<Integer> list = new ArrayList<>();
		int sum=0;
		sumTree(root, 0, list);
		for (Integer item :
				list) {
			sum+=item;
		}
		return sum;
	}


	private void sumTree(TreeNode root, int lastAns, List<Integer> list){
		int temp = lastAns*10+root.val;
		if (root.left==null&&root.right==null){
			list.add(temp);
		}
		if (root.left!=null){
			sumTree(root.left, temp, list);
		}
		if (root.right!=null){
			sumTree(root.right, temp, list);
		}


	}


	@Test
	public void test(){
		TreeNode node = TreeNode.stringToTreeNode("[5,4,8,1,null,1,4,7,2,null,null,5,1]");
		sumNumbers(node);
	}
}
